package com.wangzhenyu.learn.test.algorithm

//数组
@Suppress("UNUSED")
object TestArray {

    //轮转数组
    //使用额外数组    时间复杂度：O(n),空间复杂度：O(n)
    fun rotate01(numbers: IntArray, k: Int) {
        val n = numbers.size
        val newArray = IntArray(n)
        for (i in 0 until n) {
            newArray[(i + k) % n] = numbers[i]
        }
        System.arraycopy(newArray, 0, numbers, 0, n)
    }

    //环状替换   时间复杂度：O(n),空间复杂度：O(1)
    fun rotate02(numbers: IntArray, k: Int) {
        val n = numbers.size
        var time = 0
        var start = 0
        var current = 0

        while (time < n) {

            var pre = numbers[start]

            do {
                current = (current + k) % n
                val temp = numbers[current]
                numbers[current] = pre
                pre = temp

                time += 1
            } while (start != current)
            start += 1
            current += 1
        }
    }

    //数组翻转   时间复杂度：O(n),空间复杂度：O(1)
    fun rotate03(numbers: IntArray, k: Int) {

        //颠倒数组
        fun reverse(numbers: IntArray, start: Int, end: Int) {
            var before = start
            var after = end
            while (before < after) {
                val temp = numbers[before]
                numbers[before] = numbers[after]
                numbers[after] = temp
                before += 1
                after -= 1
            }
        }

        val length = numbers.size
        val num = k % length

        reverse(numbers, 0, length - 1)
        reverse(numbers, 0, num - 1)
        reverse(numbers, num, length - 1)
    }


    //加一
    fun addOne(digits: IntArray): IntArray {
        val n = digits.size
        var time = 0
        for (i in n - 1 downTo 0) {
            time = i
            val temp = digits[i] + 1
            if (temp != 10) {
                digits[i] = temp
                break
            } else digits[i] = 0
        }

        return if (time == 0 && digits[0] == 0) {
            val newArray = IntArray(n + 1) {
                0
            }
            newArray[0] = 1
            newArray
        } else digits
    }

    //寻找数组的中心下标   时间复杂度O(n)  空间复杂度O(1)
    fun pivotIndex(numbers: IntArray): Int {
        val total = numbers.sum()
        var left = 0
        for (i in numbers.indices) {
            if (left == total - left - numbers[i]) {
                return i
            } else {
                left += numbers[i]
            }
        }
        return -1
    }

    //最大连续 1 的个数   时间复杂度O(n)  空间复杂度O(1)
    fun findMaxConsecutiveOnes(numbers: IntArray): Int {
        var sum = 0
        var temp = 0
        for (i in numbers) {
            if (i == 1) {
                temp++
            } else {
                if (temp > sum) sum = temp
                temp = 0
            }
        }
        return if (sum > temp) sum else temp
    }

    //除自身以外数组的乘积   时间复杂度O(n)  空间复杂度O(1)
    fun productExceptSelf(numbers: IntArray): IntArray {
        val n = numbers.size
        val answer = IntArray(n)
        answer[0] = 1
        for (i in 1 until n) {
            answer[i] = answer[i - 1] * numbers[i - 1]
        }
        var temp = 1
        for (i in n - 1 downTo 0) {
            answer[i] = answer[i] * temp
            temp *= numbers[i]
        }
        return answer
    }

    //对角线遍历    时间复杂度O(m*n)  空间复杂度O(1)
    fun findDiagonalOrder(mat: Array<IntArray>): IntArray {
        val m = mat.size
        val n = mat[0].size
        val res = IntArray(m * n)
        var index = 0

        for (i in 0..m + n - 2) {
            if (i % 2 == 0) {
                //向上的对角线
                var x = if (i < m) i else m - 1
                var y = if (i < m) 0 else i - m + 1
                while (x >= 0 && y < n) {
                    res[index] = mat[x][y]
                    x -= 1
                    y += 1
                    index += 1
                }

            } else {
                var x = if (i < n) 0 else i - n + 1
                var y = if (i < n) i else n - 1
                while (x < m && y >= 0) {
                    res[index] = mat[x][y]
                    index += 1
                    x += 1
                    y -= 1
                }

            }
        }
        return res
    }

    //旋转图像   时间复杂度O(n*n)  空间复杂度O(n*n)
    fun rotate(matrix: Array<IntArray>) {

        val n = matrix.size
        val newMatrix = Array(n) {
            IntArray(n)
        }

        for (x in 0 until n) {
            for (y in 0 until n) {
                newMatrix[y][n - 1 - x] = matrix[x][y]
            }
        }
        for (x in 0 until n) {
            for (y in 0 until n) {
                matrix[x][y] = newMatrix[x][y]
            }
        }
    }

    //矩阵置零   时间复杂度O(mn)  空间复杂度O(1)
    fun setZeroes(matrix: Array<IntArray>) {
        val m = matrix.size
        val n = matrix[0].size
        var mFlag = false
        var nFlag = false

        for (i in 0 until m) {
            if (matrix[i][0] == 0) mFlag = true
        }

        for (i in 0 until n) {
            if (matrix[0][i] == 0) nFlag = true
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
        }

        if (mFlag) {
            for (i in 0 until m) {
                matrix[i][0] = 0
            }
        }

        if (nFlag) {
            for (i in 0 until n) {
                matrix[0][i] = 0
            }
        }

    }

    //螺旋矩阵   时间复杂度O(mn)  空间复杂度O(1)
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {

        val list = mutableListOf<Int>()
        val m = matrix.size
        val n = matrix[0].size

        var left = 0
        var right = n - 1
        var top = 0
        var bottom = m - 1

        while (left <= right && top <= bottom) {

            for (i in left..right) {
                list.add(matrix[top][i])
            }


            for (i in top + 1..bottom) {
                list.add(matrix[i][right])
            }

            if (left < right && top < bottom) {

                for (i in right - 1 downTo left) {
                    list.add(matrix[bottom][i])
                }
                for (i in bottom - 1 downTo top + 1) {
                    list.add(matrix[i][left])
                }
            }

            left++
            right--
            top++
            bottom--
        }

        return list
    }

    //螺旋矩阵 II   时间复杂度O(n*n)  空间复杂度O(1)
    fun generateMatrix(n: Int): Array<IntArray> {

        val matrix = Array(n) {
            IntArray(n)
        }

        var left = 0
        var right = n - 1
        var top = 0
        var bottom = n - 1

        var temp = 0

        while (left <= right && top <= bottom) {

            for (i in left..right) {
                temp++
                matrix[top][i] = temp
            }

            for (i in top + 1..bottom) {
                temp++
                matrix[i][right] = temp
            }

            if (left < right && top < bottom) {

                for (i in right - 1 downTo left) {
                    temp++
                    matrix[bottom][i] = temp
                }
                for (i in bottom - 1 downTo top + 1) {
                    temp++
                    matrix[i][left] = temp
                }
            }

            left++
            right--
            top++
            bottom--
        }

        return matrix
    }

    //生命游戏   时间复杂度O(n*n)  空间复杂度O(1)
    fun gameOfLife(board: Array<IntArray>) {

        val rows = board.size
        val cols = board[0].size
        val typeArray = intArrayOf(-1, 0, 1)

        //对矩阵中每一个元素进行遍历，计算其周围八个数的总和
        for (i in 0 until rows) {
            for (j in 0 until cols) {

                //计算周围八个细胞的总和
                var temp = 0

                for (m in 0..2) {
                    for (n in 0..2) {
                        if (!((typeArray[m] == 0 && typeArray[n] == 0)
                                    || i < -typeArray[m]
                                    || i >= rows - typeArray[m]
                                    || j < -typeArray[n]
                                    || j >= cols - typeArray[n]
                                    )
                        ) {
                            //表示原来为1
                            if (board[i + typeArray[m]][j + typeArray[n]] == 1
                                || board[i + typeArray[m]][j + typeArray[n]] == -1
                            )
                                temp += 1
                        }
                    }
                }

                if (board[i][j] == 1 && (temp != 3 && temp != 2)) {
                    board[i][j] = -1
                }

                if (board[i][j] == 0 && temp == 3) {
                    //此时细胞复活了
                    board[i][j] = 2
                }

            }
        }

        for (i in 0 until rows) {
            for (j in 0 until cols) {
                if (board[i][j] == -1) {
                    board[i][j] = 0
                }
                if (board[i][j] == 2) {
                    board[i][j] = 1
                }
            }
        }

    }

    //排序

}